package design;

import java.util.HashMap;
import java.util.Map;

/**
 * @description: TODO
 * @author: mayunfei
 * @date: 2024/12/7 10:22
 */
public class LRUCache {

    int capacity;
    int size;
    Node head;
    Node tail;
    Map<Integer, Node> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.head = new Node();
        this.tail = new Node();
        this.head.next = tail;
        this.tail.pre = head;
        this.map = new HashMap<>();
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node == null) {
            node = new Node(key, value);
            if (size == capacity) {
                addToHead(node);
                map.put(key, node);
                map.remove(tail.pre.key);
                remove(tail.pre);
            } else {
                size++;
                addToHead(node);
                map.put(key, node);
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(Node node) {
        node.next = head.next;
        node.pre = head;
        head.next = node;
        node.next.pre = node;
    }

    private void remove(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        node.next = null;
        node.pre = null;
    }

    private void moveToHead(Node node) {
        remove(node);
        addToHead(node);
    }

    public class Node {
        int key;
        int value;
        Node pre;
        Node next;

        Node() {}

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    /**
     *
     *LRUCache lruCache = new LRUCache(2);
     *         lruCache.put(1, 1);
     *         lruCache.put(2, 2);
     *         lruCache.get(1);
     *         lruCache.put(3, 3);
     *         lruCache.get(2);
     *         lruCache.put(4, 4);
     *         lruCache.get(1);
     *         lruCache.get(3);
     *         lruCache.get(4);
     */
}
